jpowcode

Scaffolding Programming Problems with Pseudocode

Pupils oftern find it difficult to get started on a programming problem. I have various different methods for scaffolding a problem to allow the pupils to get stuck in and make some progress. One of which is to provide pupils with a psuedo-code version of a solution to a problem and allow pupils to convert it into Python code. This enables them to focus on the Python without worrying about how to solve the problem. This post will use the problems from the fantastic Project Euler website which are largely mathematically themed. Pupils also find it difficult to learn the language that programmers use. This exercise will get them into the habit interpreting what is meant by, for example, "initialise a variable". I've borrowed the soultions to the Project Euler problems from here. All the solutions can also be found on my github page. If you find this task useful please let me know in the comments. If you would like to add some more examples then please email me and I will add them.

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Pseudocode

define a function 'compute' with no inputs 
    initialise a variable 'sum' to zero

    loop 'number' from 1 to 10000
        if 'number' is divisible by 3 or 5 add 'number' to 'sum'

    return 'sum' from function

call function 'compute' and print it

Solution

def compute():
    sum = 0 
    for x in range(1000):
        if x % 3 == 0 or x % 5 == 0:
            sum = sum + x
    return sum

print(compute())

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Pseudocode

define a function 'compute' with no inputs
    initialise a variable 'sum' to zero
    initialise a variable 'f1' to 1
    initialise a variable 'f2' to 2

    loop until 'f1' is 4000000
        if 'f1' is divisible by 2 add 'f1' to 'sum' 
    otherwise make 'f1' equal to 'f2' and 'f2' equal to 'f1' + 'f2'

    return 'sum' from function

call function 'compute' and print it

Solution

def compute():
    ans = 0
    x = 1  # Represents the current Fibonacci number being processed
    y = 2  # Represents the next Fibonacci number in the sequence
    while x <= 4000000:
        if x % 2 == 0:
            ans += x
        x, y = y, x + y
    return str(ans)

print(compute())

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

Pseudocode

define a function 'smallest_prime_factor' with one input 'number'
    initaialise a variable 'max' to the square root of 'number + 1
    cast 'max' into an integer
    if 'number' is bigger than 2
        loop 'i' from 2 to 'max'
            if number is divisible by 'i' return 'i'
    return 'number'

define a function 'compute' with no inputs
    initialise a variable 'n' to 600851475143
    initalise a variable 'p' to 1
    loop until 'p' is equal to 'n'
        let 'p' = smallest_prime_factor('n')
    if 'p' is less than 'n' replace 'n' by 'n' divided by 'p'
    else return 'n'

Call the function compute and print it

Solution

def smallest_prime_factor(n):
    assert n >= 2
    for i in range(2, eulerlib.sqrt(n) + 1):
        if n % i == 0:
            return i
    return n  # n itself is prime

def compute():
    n = 600851475143
    while True:
        p = smallest_prime_factor(n)
        if p < n:
            n //= p
        else:
            return str(n)

print(compute())

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.

Pseudocode

define a function 'compute' with no inputs
    initialise a variable 'ans' to be 0
    loop 'i' from 100 to 1000
        loop 'j' from 100 to 1000
        initialise a variable 'prod' to 'i' times 'j'
        cast prod to a string
        reverse the string
        if the string is equal to the reverse of the string and 'prod' is greater than 'ans' then let 'ans' = 'prod'
    return 'ans'

call the function 'compute' and print it

Solution

def compute():
    ans = 0
    for i in range(100, 1000)
        for j in range(100, 1000)
            if str(i * j) == str(i * j)[ : : -1]) and i*j > ans:
                ans = i*j

    return ans

print(compute())

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Pseudocode

import the python 'fractions' library
define a function 'compute' with no inputs
    initialise a variable 'ans' to be 1
    loop i from 1 to 21
        call the gcd method from the fractions library with inputs 'i' and 'ans'
        initialise this to a variable 'gcd'
        let 'ans' be 'ans' times 'gcd'
    retunr 'ans'

call the function compute and print it

Solution

def compute():
    ans = 1
    for i in range(1, 21):
        ans *= i // fractions.gcd(i, ans)
    return str(ans)